#include<iostream>
using namespace std;
const int N=1e6+5;
int f[N],n,T,ans[N];
void solve()
{
    f[1]=f[2]=1;
    for(int i=3;i<=N;i++)
    {
        f[i]=f[i-1]%9+f[i-2]%9;
        f[i]%=9;
    }
    for(int i=1;i<=N;i++)
    {
        ans[i]=(ans[i-1]+f[i])%9;
    }
}
int main()
{
    cin>>T;
    solve();
    while(T--)
    {
        scanf("%d",&n);
       // for(int i=1;i<=n;i++)
          //  printf("%d\n",ans[i]);
        printf("%d\n",ans[n]);
    }
    return 0;
}